{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sentence Alignment\n",
    "\n",
    "## Reference\n",
    "\n",
    "- [組合せ最適化入門](https://www.jstage.jst.go.jp/article/jnlp/21/5/21_1059/_pdf)\n",
    "- [http://www.nltk.org/book-jp/ch12.html](http://www.nltk.org/book-jp/ch12.html)\n",
    "\n",
    "## Data Source\n",
    "\n",
    "- [Transcript of Jobs' commencement speech - slashdot](https://slashdot.org/comments.pl?sid=152625&cid=12810404)\n",
    "- [PSTY.Net備忘録](https://psty.tumblr.com/post/9502833615/%E5%B8%82%E6%9D%91%E4%BD%90%E7%99%BB%E7%BE%8E%E3%81%95%E3%82%93%E7%BF%BB%E8%A8%B3%E3%81%AB%E3%82%88%E3%82%8Bsteve-jobs%E6%B0%8F%E3%81%AE-%E3%82%B9%E3%83%94%E3%83%BC%E3%83%81%E5%85%A8%E6%96%87%E3%81%AF%E4%BB%A5%E4%B8%8B%E3%81%AE%E9%80%9A%E3%82%8A%E3%81%A7%E3%81%99)\n",
    "- [Tanaka Corpus](http://www.edrdg.org/wiki/index.php/Tanaka_Corpus)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "original_text = \"\"\"Thank you. I'm honored to be with you today for your commencement from one of the finest universities in the world. Truth be told, I never graduated from college and this is the closest I've ever gotten to a college graduation.\n",
    "\n",
    "Today I want to tell you three stories from my life. That's it. No big deal. Just three stories. The first story is about connecting the dots.\n",
    "\n",
    "I dropped out of Reed College after the first six months but then stayed around as a drop-in for another eighteen months or so before I really quit. So why did I drop out? It started before I was born. My biological mother was a young, unwed graduate student, and she decided to put me up for adoption. She felt very strongly that I should be adopted by college graduates, so everything was all set for me to be adopted at birth by a lawyer and his wife, except that when I popped out, they decided at the last minute that they really wanted a girl. So my parents, who were on a waiting list, got a call in the middle of the night asking, \"We've got an unexpected baby boy. Do you want him?\" They said, \"Of course.\" My biological mother found out later that my mother had never graduated from college and that my father had never graduated from high school. She refused to sign the final adoption papers. She only relented a few months later when my parents promised that I would go to college.\n",
    "\n",
    "This was the start in my life. And seventeen years later, I did go to college, but I naïvely chose a college that was almost as expensive as Stanford, and all of my working-class parents' savings were being spent on my college tuition. After six months, I couldn't see the value in it. I had no idea what I wanted to do with my life, and no idea of how college was going to help me figure it out, and here I was, spending all the money my parents had saved their entire life. So I decided to drop out and trust that it would all work out OK. It was pretty scary at the time, but looking back, it was one of the best decisions I ever made. The minute I dropped out, I could stop taking the required classes that didn't interest me and begin dropping in on the ones that looked far more interesting.\n",
    "\n",
    "It wasn't all romantic. I didn't have a dorm room, so I slept on the floor in friends' rooms. I returned Coke bottles for the five-cent deposits to buy food with, and I would walk the seven miles across town every Sunday night to get one good meal a week at the Hare Krishna temple. I loved it. And much of what I stumbled into by following my curiosity and intuition turned out to be priceless later on. Let me give you one example.\n",
    "\n",
    "Reed College at that time offered perhaps the best calligraphy instruction in the country. Throughout the campus every poster, every label on every drawer was beautifully hand-calligraphed. Because I had dropped out and didn't have to take the normal classes, I decided to take a calligraphy class to learn how to do this. I learned about serif and sans-serif typefaces, about varying the amount of space between different letter combinations, about what makes great typography great. It was beautiful, historical, artistically subtle in a way that science can't capture, and I found it fascinating.\n",
    "\n",
    "None of this had even a hope of any practical application in my life. But ten years later when we were designing the first Macintosh computer, it all came back to me, and we designed it all into the Mac. It was the first computer with beautiful typography. If I had never dropped in on that single course in college, the Mac would have never had multiple typefaces or proportionally spaced fonts, and since Windows just copied the Mac, it's likely that no personal computer would have them.\n",
    "\n",
    "If I had never dropped out, I would have never dropped in on that calligraphy class and personals computers might not have the wonderful typography that they do.\n",
    "\n",
    "Of course it was impossible to connect the dots looking forward when I was in college, but it was very, very clear looking backwards 10 years later. Again, you can't connect the dots looking forward. You can only connect them looking backwards, so you have to trust that the dots will somehow connect in your future. You have to trust in something--your gut, destiny, life, karma, whatever--because believing that the dots will connect down the road will give you the confidence to follow your heart, even when it leads you off the well-worn path, and that will make all the difference.\n",
    "\n",
    "My second story is about love and loss. I was lucky. I found what I loved to do early in life. Woz and I started Apple in my parents' garage when I was twenty. We worked hard and in ten years, Apple had grown from just the two of us in a garage into a $2 billion company with over 4,000 employees. We'd just released our finest creation, the Macintosh, a year earlier, and I'd just turned thirty, and then I got fired. How can you get fired from a company you started? Well, as Apple grew, we hired someone who I thought was very talented to run the company with me, and for the first year or so, things went well. But then our visions of the future began to diverge, and eventually we had a falling out. When we did, our board of directors sided with him, and so at thirty, I was out, and very publicly out. What had been the focus of my entire adult life was gone, and it was devastating. I really didn't know what to do for a few months. I felt that I had let the previous generation of entrepreneurs down, that I had dropped the baton as it was being passed to me. I met with David Packard and Bob Noyce and tried to apologize for screwing up so badly. I was a very public failure and I even thought about running away from the Valley. But something slowly began to dawn on me. I still loved what I did. The turn of events at Apple had not changed that one bit. I'd been rejected but I was still in love. And so I decided to start over.\n",
    "\n",
    "I didn't see it then, but it turned out that getting fired from Apple was the best thing that could have ever happened to me. The heaviness of being successful was replaced by the lightness of being a beginner again, less sure about everything. It freed me to enter one of the most creative periods in my life. During the next five years I started a company named NeXT, another company named Pixar and fell in love with an amazing woman who would become my wife. Pixar went on to create the world's first computer-animated feature film, \"Toy Story,\" and is now the most successful animation studio in the world.\n",
    "\n",
    "In a remarkable turn of events, Apple bought NeXT and I returned to Apple and the technology we developed at NeXT is at the heart of Apple's current renaissance, and Lorene and I have a wonderful family together.\n",
    "\n",
    "I'm pretty sure none of this would have happened if I hadn't been fired from Apple. It was awful-tasting medicine but I guess the patient needed it. Sometimes life's going to hit you in the head with a brick. Don't lose faith. I'm convinced that the only thing that kept me going was that I loved what I did. You've got to find what you love, and that is as true for work as it is for your lovers. Your work is going to fill a large part of your life, and the only way to be truly satisfied is to do what you believe is great work, and the only way to do great work is to love what you do. If you haven't found it yet, keep looking, and don't settle. As with all matters of the heart, you'll know when you find it, and like any great relationship it just gets better and better as the years roll on. So keep looking. Don't settle.\n",
    "\n",
    "My third story is about death. When I was 17 I read a quote that went something like \"If you live each day as if it was your last, someday you'll most certainly be right.\" It made an impression on me, and since then, for the past 33 years, I have looked in the mirror every morning and asked myself, \"If today were the last day of my life, would I want to do what I am about to do today?\" And whenever the answer has been \"no\" for too many days in a row, I know I need to change something. Remembering that I'll be dead soon is the most important thing I've ever encountered to help me make the big choices in life, because almost everything--all external expectations, all pride, all fear of embarrassment or failure--these things just fall away in the face of death, leaving only what is truly important. Remembering that you are going to die is the best way I know to avoid the trap of thinking you have something to lose. You are already naked. There is no reason not to follow your heart.\n",
    "\n",
    "About a year ago, I was diagnosed with cancer. I had a scan at 7:30 in the morning and it clearly showed a tumor on my pancreas. I didn't even know what a pancreas was. The doctors told me this was almost certainly a type of cancer that is incurable, and that I should expect to live no longer than three to six months. My doctor advised me to go home and get my affairs in order, which is doctors' code for \"prepare to die.\" It means to try and tell your kids everything you thought you'd have the next ten years to tell them, in just a few months. It means to make sure that everything is buttoned up so that it will be as easy as possible for your family. It means to say your goodbyes.\n",
    "\n",
    "I lived with that diagnosis all day. Later that evening I had a biopsy where they stuck an endoscope down my throat, through my stomach into my intestines, put a needle into my pancreas and got a few cells from the tumor. I was sedated but my wife, who was there, told me that when they viewed the cells under a microscope, the doctor started crying, because it turned out to be a very rare form of pancreatic cancer that is curable with surgery. I had the surgery and, thankfully, I am fine now.\n",
    "\n",
    "This was the closest I've been to facing death, and I hope it's the closest I get for a few more decades. Having lived through it, I can now say this to you with a bit more certainty than when death was a useful but purely intellectual concept. No one wants to die, even people who want to go to Heaven don't want to die to get there, and yet, death is the destination we all share. No one has ever escaped it. And that is as it should be, because death is very likely the single best invention of life. It's life's change agent; it clears out the old to make way for the new. right now, the new is you. But someday, not too long from now, you will gradually become the old and be cleared away. Sorry to be so dramatic, but it's quite true. Your time is limited, so don't waste it living someone else's life. Don't be trapped by dogma, which is living with the results of other people's thinking. Don't let the noise of others' opinions drown out your own inner voice, heart and intuition. They somehow already know what you truly want to become. Everything else is secondary.\n",
    "\n",
    "When I was young, there was an amazing publication called The Whole Earth Catalogue, which was one of the bibles of my generation. It was created by a fellow named Stuart Brand not far from here in Menlo Park, and he brought it to life with his poetic touch. This was in the late Sixties, before personal computers and desktop publishing, so it was all made with typewriters, scissors, and Polaroid cameras. it was sort of like Google in paperback form thirty-five years before Google came along. I was idealistic, overflowing with neat tools and great notions. Stuart and his team put out several issues of the The Whole Earth Catalogue, and then when it had run its course, they put out a final issue. It was the mid-Seventies and I was your age. On the back cover of their final issue was a photograph of an early morning country road, the kind you might find yourself hitchhiking on if you were so adventurous. Beneath were the words, \"Stay hungry, stay foolish.\" It was their farewell message as they signed off. \"Stay hungry, stay foolish.\" And I have always wished that for myself, and now, as you graduate to begin anew, I wish that for you. Stay hungry, stay foolish.\n",
    "\n",
    "Thank you all, very much.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "japanese_text = \"\"\"ありがとう。世界有数の最高学府を卒業される皆さんと、本日こうして晴れの門出に同席でき大変光栄です。実を言うと私は大学を出たことがないので、これが今までで最も大学卒業に近い経験ということになります。\n",
    "\n",
    "本日は皆さんに私自身の人生から得たストーリーを３つ紹介します。それだけです。どうってことないですよね、たった３つです。最初の話は、点と点を繋ぐというお話です。\n",
    "\n",
    "私はリード大学を半年で退学しました。が、本当にやめてしまうまで18ヶ月かそこらはまだ大学に居残って授業を聴講していました。じゃあ、なぜ辞めたんだ？ということになるんですけども、それは私が生まれる前の話に遡ります。\n",
    "\n",
    "私の生みの母親は若い未婚の院生で、私のことは生まれたらすぐ養子に出すと決めていました。育ての親は大卒でなくては、そう彼女は固く思い定めていたので、ある弁護士の夫婦が出産と同時に私を養子として引き取ることで手筈はすべて整っていたんですね。ところがいざ私がポンと出てしまうと最後のギリギリの土壇場になってやっぱり女の子が欲しいということになってしまった。で、養子縁組待ちのリストに名前が載っていた今の両親のところに夜も遅い時間に電話が行ったんです。「予定外の男の赤ちゃんが生まれてしまったんですけど、欲しいですか？」。彼らは「もちろん」と答えました。\n",
    "\n",
    "しかし、これは生みの母親も後で知ったことなんですが、二人のうち母親の方は大学なんか一度だって出ていないし父親に至っては高校もロクに出ていないわけです。そうと知った生みの母親は養子縁組の最終書類にサインを拒みました。そうして何ヶ月かが経って今の親が将来私を大学に行かせると約束したので、さすがの母親も態度を和らげた、といういきさつがありました。\n",
    "\n",
    "こうして私の人生はスタートしました。やがて17年後、私は本当に大学に入るわけなんだけど、何も考えずにスタンフォード並みに学費の高いカレッジを選んでしまったもんだから労働者階級の親の稼ぎはすべて大学の学費に消えていくんですね。そうして6ヶ月も過ぎた頃には、私はもうそこに何の価値も見 出せなくなっていた。自分が人生で何がやりたいのか私には全く分からなかったし、それを見つける手助けをどう大学がしてくれるのかも全く分からない。なのに自分はここにいて、親が生涯かけて貯めた金を残らず使い果たしている。だから退学を決めた。全てのことはうまく行くと信じてね。\n",
    "\n",
    "そりゃ当時はかなり怖かったですよ。ただ、今こうして振り返ってみると、あれは人生最良の決断だったと思えます。だって退学した瞬間から興味のない必修科目はもう採る必要がないから、そういうのは止めてしまって、その分もっともっと面白そうなクラスを聴講しにいけるんですからね。\n",
    "\n",
    "夢物語とは無縁の暮らしでした。寮に自分の持ち部屋がないから夜は友達の部屋の床に寝泊りさせてもらってたし、コーラの瓶を店に返すと5セント玉がもらえるんだけど、あれを貯めて食費に充てたりね。日曜の夜はいつも７マイル歩いて街を抜けると、ハーレクリシュナ寺院でやっとまともなメシにありつける、これが無茶苦茶旨くてね。\n",
    "\n",
    "しかし、こうして自分の興味と直感の赴くまま当時身につけたことの多くは、あとになって値札がつけられないぐらい価値のあるものだって分かってきたんだね。\n",
    "ひとつ具体的な話をしてみましょう。\n",
    "\n",
    "リード大学は、当時としてはおそらく国内最高水準のカリグラフィ教育を提供する大学でした。キャンパスのそれこそ至るところ、ポスター1枚から戸棚のひとつひとつに貼るラベルの1枚1枚まで美しい手書きの飾り文字が施されていました。私は退学した身。もう普通のクラスには出なくていい。そこでとりあえずカリグラフィのクラスを採って、どうやったらそれができるのか勉強してみることに決めたんです。\n",
    "\n",
    "セリフをやってサンセリフの書体もやって、あとは活字の組み合わせに応じて字間を調整する手法を学んだり、素晴らしいフォントを実現するためには何が必要かを学んだり。それは美しく、歴史があり、科学では判別できない微妙なアートの要素を持つ世界で、いざ始めてみると私はすっかり夢中になってしまったんですね。\n",
    "\n",
    "こういったことは、どれも生きていく上で何ら実践の役に立ちそうのないものばかりです。だけど、それから10年経って最初のマッキントッシュ・コンピュータを設計する段になって、この時の経験が丸ごと私の中に蘇ってきたんですね。で、僕たちはその全てをマックの設計に組み込んだ。そうして完成したのは、美しいフォント機能を備えた世界初のコンピュータでした。\n",
    "\n",
    "もし私が大学であのコースひとつ寄り道していなかったら、マックには複数書体も字間調整フォントも入っていなかっただろうし、ウィンドウズはマックの単なるパクりに過ぎないので、パソコン全体で見回してもそうした機能を備えたパソコンは地上に1台として存在しなかったことになります。\n",
    "\n",
    "もし私が退学していなかったら、あのカリグラフィのクラスには寄り道していなかった。\n",
    "\n",
    "そして、パソコンには今あるような素晴らしいフォントが搭載されていなかった。\n",
    "もちろん大学にいた頃の私には、まだそんな先々のことまで読んで点と点を繋げてみることなんてできませんでしたよ。だけど10年後振り返ってみると、これほどまたハッキリクッキリ見えることもないわけで、そこなんだよね。もう一度言います。未来に先回りして点と点を繋げて見ることはできない、君たちにできるのは過去を振り返って繋げることだけなんだ。だからこそバラバラの点であっても将来それが何らかのかたちで必ず繋がっていくと信じなくてはならない。自分の根性、運命、人生、カルマ…何でもいい、とにかく信じること。点と点が自分の歩んでいく道の途上のどこかで必ずひとつに繋がっていく、そう信じることで君たちは確信を持って己の心の赴くまま生きていくことができる。結果、人と違う道を行くことになってもそれは同じ。信じることで全てのことは、間違いなく変わるんです。\n",
    "\n",
    "２番目の話は、愛と敗北にまつわるお話です。\n",
    "\n",
    "私は幸運でした。自分が何をしたいのか、人生の早い段階で見つけることができた。実家のガレージでウォズとアップルを始めたのは、私が二十歳の時でした。がむしゃらに働いて10年後、アップルはガレージの我々たった二人の会社から従業員4千人以上の20億ドル企業になりました。そうして自分たちが 出しうる最高の作品、マッキントッシュを発表してたった1年後、30回目の誕生日を迎えたその矢先に私は会社を、クビになったんです。\n",
    "\n",
    "自分が始めた会社だろ？どうしたらクビになるんだ？と思われるかもしれませんが、要するにこういうことです。アップルが大きくなったので私の右腕として会社を動かせる非常に有能な人間を雇った。そして最初の1年かそこらはうまく行った。けど互いの将来ビジョンにやがて亀裂が生じ始め、最後は物別れ に終わってしまった。いざ決裂する段階になって取締役会議が彼に味方したので、齢30にして会社を追い出されたと、そういうことです。しかも私が会社を放逐されたことは当時大分騒がれたので、世の中の誰もが知っていた。\n",
    "\n",
    "自分が社会人生命の全てをかけて打ち込んできたものが消えたんですから、私はもうズタズタでした。数ヶ月はどうしたらいいのか本当に分からなかった。自分のせいで前の世代から受け継いだ起業家たちの業績が地に落ちた、自分は自分に渡されたバトンを落としてしまったんだ、そう感じました。このように 最悪のかたちで全てを台無しにしてしまったことを詫びようと、デイヴィッド・パッカードとボブ・ノイスにも会いました。知る人ぞ知る著名な落伍者となったことで一時はシリコンヴァレーを離れることも考えたほどです。\n",
    "\n",
    "ところが、そうこうしているうちに少しずつ私の中で何かが見え始めてきたんです。私はまだ自分のやった仕事が好きでした。アップルでのイザコザはその気持ちをいささかも変えなかった。振られても、まだ好きなんですね。だからもう一度、一から出直してみることに決めたんです。\n",
    "\n",
    "その時は分からなかったのですが、やがてアップルをクビになったことは自分の人生最良の出来事だったのだ、ということが分かってきました。成功者であることの重み、それがビギナーであることの軽さに代わった。そして、あらゆる物事に対して前ほど自信も持てなくなった代わりに、自由になれたことで私 はまた一つ、自分の人生で最もクリエイティブな時代の絶頂期に足を踏み出すことができたんですね。\n",
    "\n",
    "それに続く5年のうちに私はNeXTという会社を始め、ピクサーという会社を作り、素晴らしい女性と恋に落ち、彼女は私の妻になりました。\n",
    "ピクサーはやがてコンピュータ・アニメーションによる世界初の映画「トイ・ストーリー」を創り、今では世界で最も成功しているアニメーション・スタジオです。\n",
    "\n",
    "思いがけない方向に物事が運び、NeXTはアップルが買収し、私はアップルに復帰。NeXTで開発した技術は現在アップルが進める企業再生努力の中心にあります。ロレーヌと私は一緒に素晴らしい家庭を築いてきました。\n",
    "\n",
    "アップルをクビになっていなかったらこうした事は何ひとつ起こらなかった、私にはそう断言できます。そりゃひどい味の薬でしたよ。でも患者にはそれが必要なんだろうね。人生には時としてレンガで頭をぶん殴られるようなひどいことも起こるものなのです。だけど、信念を放り投げちゃいけない。私が挫けずにやってこれたのはただ一つ、自分のやっている仕事が好きだという、その気持ちがあったからです。皆さんも自分がやって好きなことを見つけなきゃいけない。それは仕事も恋愛も根本は同じで、君たちもこれから仕事が人生の大きなパートを占めていくだろうけど自分が本当に心の底から満足を得たいなら進む道は ただ一つ、自分が素晴しいと信じる仕事をやる、それしかない。そして素晴らしい仕事をしたいと思うなら進むべき道はただ一つ、好きなことを仕事にすることなんですね。まだ見つかってないなら探し続ければいい。落ち着いてしまっちゃ駄目です。心の問題と一緒でそういうのは見つかるとすぐピンとくるものだし、 素晴らしい恋愛と同じで年を重ねるごとにどんどんどんどん良くなっていく。だから探し続けること。落ち着いてしまってはいけない。\n",
    "\n",
    "３つ目は、死に関するお話です。\n",
    "\n",
    "私は17の時、こんなような言葉をどこかで読みました。確かこうです。「来る日も来る日もこれが人生最後の日と思って生きるとしよう。そうすればいずれ必ず、間違いなくその通りになる日がくるだろう」。それは私にとって強烈な印象を与える言葉でした。そしてそれから現在に至るまで33年間、私は毎朝鏡を見て自分にこう問い掛けるのを日課としてきました。「もし今日が自分の人生最後の日だとしたら、今日やる予定のことを私は本当にやりたいだろうか？」。それに対する答えが“NO”の日が幾日も続くと、そろそろ何かを変える必要があるなと、そう悟るわけです。\n",
    "\n",
    "自分が死と隣り合わせにあることを忘れずに思うこと。これは私がこれまで人生を左右する重大な選択を迫られた時には常に、決断を下す最も大きな手掛かりとなってくれました。何故なら、ありとあらゆる物事はほとんど全て外部からの期待の全て、己のプライドの全て、屈辱や挫折に対する恐怖の全て…こ ういったものは我々が死んだ瞬間に全て、きれいサッパリ消え去っていく以外ないものだからです。そして後に残されるのは本当に大事なことだけ。自分もいつかは死ぬ。そのことを思い起こせば自分が何か失ってしまうんじゃないかという思考の落とし穴は回避できるし、これは私の知る限り最善の防御策です。\n",
    "\n",
    "君たちはもう素っ裸なんです。自分の心の赴くまま生きてならない理由など、何一つない。\n",
    "\n",
    "\n",
    "今から1年ほど前、私は癌と診断されました。 朝の7時半にスキャンを受けたところ、私のすい臓にクッキリと腫瘍が映っていたんですね。私はその時まで、すい臓が何かも知らなかった。\n",
    "\n",
    "医師たちは私に言いました。これは治療不能な癌の種別である、ほぼ断定していいと。生きて3ヶ月から6ヶ月、それ以上の寿命は望めないだろう、と。主治医は家に帰って仕事を片付けるよう、私に助言しました。これは医師の世界では「死に支度をしろ」という意味のコード（符牒）です。\n",
    "\n",
    "それはつまり、子どもたちに今後10年の間に言っておきたいことがあるのなら思いつく限り全て、なんとか今のうちに伝えておけ、ということです。たった数ヶ月でね。それはつまり自分の家族がなるべく楽な気持ちで対処できるよう万事しっかりケリをつけろ、ということです。それはつまり、さよならを告げる、ということです。\n",
    "\n",
    "私はその診断結果を丸1日抱えて過ごしました。そしてその日の夕方遅く、生検を受け、喉から内視鏡を突っ込んで中を診てもらったんですね。内視鏡は胃を通って腸内に入り、そこから医師たちはすい臓に針で穴を開け腫瘍の細胞を幾つか採取しました。私は鎮静剤を服用していたのでよく分 からなかったんですが、その場に立ち会った妻から後で聞いた話によると、顕微鏡を覗いた医師が私の細胞を見た途端、急に泣き出したんだそうです。何故ならそれは、すい臓癌としては極めて稀な形状の腫瘍で、手術で直せる、そう分かったからなんです。こうして私は手術を受け、ありがたいことに今も元気です。\n",
    "\n",
    "これは私がこれまで生きてきた中で最も、死に際に近づいた経験ということになります。この先何十年かは、これ以上近い経験はないものと願いたいですけどね。\n",
    "\n",
    "以前の私にとって死は、意識すると役に立つことは立つんだけど純粋に頭の中の概念に過ぎませんでした。でも、あれを経験した今だから前より多少は確信を持って君たちに言えることなんだが、誰も死にたい人なんていないんだよね。天国に行きたいと願う人ですら、まさかそこに行くために死にたいとは思わ ない。にも関わらず死は我々みんなが共有する終着点なんだ。かつてそこから逃れられた人は誰一人としていない。そしてそれは、そうあるべきことだら、そういうことになっているんですよ。何故と言うなら、死はおそらく生が生んだ唯一無比の、最高の発明品だからです。それは生のチェンジエージェント、要するに 古きものを一掃して新しきものに道筋を作っていく働きのあるものなんです。今この瞬間、新しきものと言ったらそれは他ならぬ君たちのことだ。しかしいつか遠くない将来、その君たちもだんだん古きものになっていって一掃される日が来る。とてもドラマチックな言い草で済まんけど、でもそれが紛れもない真実なんです。\n",
    "\n",
    "君たちの時間は限られている。だから自分以外の他の誰かの人生を生きて無駄にする暇なんかない。ドグマという罠に、絡め取られてはいけない。それは他の人たちの考え方が生んだ結果とともに生きていくということだからね。その他大勢の意見の雑音に自分の内なる声、心、直感を掻き消されないことです。自分の内なる声、心、直感というのは、どうしたわけか君が本当になりたいことが何か、もうとっくの昔に知っているんだ。だからそれ以外のことは全て、二の次でいい。\n",
    "\n",
    "私が若い頃、「全地球カタログ」というとんでもない出版物があって、同世代の間ではバイブルの一つになっていました。\n",
    "\n",
    "それはスチュアート・ブランドという男がここからそう遠くないメンローパークで製作したもので、彼の詩的なタッチが誌面を実に生き生きしたものに仕上げていました。時代は60年代後半。パソコンやデスクトップ印刷がまだ普及する前の話ですから、媒体は全てタイプライターとはさみ、ポラロイドカメラで作っていた。だけど、それはまるでグーグルが出る35年前の時代に遡って出されたグーグルのペーパーバック版とも言うべきもので、理想に輝き、使えるツールと偉大な概念がそれこそページの端から溢れ返っている、そんな印刷物でした。\n",
    "\n",
    "スチュアートと彼のチームはこの「全地球カタログ」の発行を何度か重ね、コースを一通り走り切ってしまうと最終号を出した。それが70年代半ば。私はちょうど今の君たちと同じ年頃でした。\n",
    "\n",
    "最終号の背表紙には、まだ朝早い田舎道の写真が1枚ありました。君が冒険の好きなタイプならヒッチハイクの途上で一度は出会う、そんな田舎道の写真です。写真の下にはこんな言葉が書かれていました。「ハングリーであれ。馬鹿であれ。」。それが断筆する彼らが最後に残した、お別れのメッセージでした。「Stay hungry, stay foolish.」\n",
    "\n",
    "それからというもの私は常に自分自身そうありたいと願い続けてきた。そして今、卒業して新たな人生に踏み出す君たちに、それを願って止みません。\n",
    "\n",
    "ハングリーであれ。馬鹿であれ。\n",
    "\n",
    "ご清聴ありがとうございました。\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--2020-09-13 23:56:17--  ftp://ftp.monash.edu/pub/nihongo/examples.utf.gz\n",
      "           => ‘data/examples.utf.gz’\n",
      "Resolving ftp.monash.edu (ftp.monash.edu)... 2001:388:608c:8c1:250:56ff:feb5:3ef7, 130.194.20.68\n",
      "Connecting to ftp.monash.edu (ftp.monash.edu)|2001:388:608c:8c1:250:56ff:feb5:3ef7|:21... connected.\n",
      "Logging in as anonymous ... Logged in!\n",
      "==> SYST ... done.    ==> PWD ... done.\n",
      "==> TYPE I ... done.  ==> CWD (1) /pub/nihongo ... done.\n",
      "==> SIZE examples.utf.gz ... 9644611\n",
      "==> EPSV ... done.    ==> RETR examples.utf.gz ... done.\n",
      "Length: 9644611 (9.2M) (unauthoritative)\n",
      "\n",
      "examples.utf.gz     100%[===================>]   9.20M   121KB/s    in 81s     \n",
      "\n",
      "2020-09-13 23:57:42 (116 KB/s) - ‘data/examples.utf.gz’ saved [9644611]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "!wget -P \"../data\" \"ftp://ftp.monash.edu/pub/nihongo/examples.utf.gz\"\n",
    "!tar -zxvf \"../data/examples.utf.gz\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the case where any sentence in documents F and E may be freely mapped to any of the sentences in documents F and E, regardless of their order of appearance.\n",
    "\n",
    "## IP formulation\n",
    "\n",
    "$$\n",
    "\\begin{array}{ll}\\text { maximize } & \\sum_{i=1}^{n_{f}} \\sum_{j=1}^{n_{e}} s_{i j} x_{i j} \\\\ \\text { subject to } & \\sum_{j=1}^{n_{e}} x_{i j} \\leq 1, \\quad i=1, \\ldots, n_{f} \\\\ & \\sum_{i=1}^{n_{f}} x_{i j} \\leq 1, \\quad j=1, \\ldots n_{e} \\\\ & x_{i j} \\in\\{0,1\\}, \\quad i=1, \\ldots, n_{f}, j=1, \\ldots, n_{e}\\end{array}\n",
    "$$\n",
    "\n",
    "## QUBO formulation\n",
    "\n",
    "$$\n",
    "\\begin{array}{ll}\n",
    "\\text { minimize } H({\\bf x}) & = - \\sum_{i=1}^{n_{f}} \\sum_{j=1}^{n_{e}} s_{i j} x_{i j} \\\\ & + \\lambda_f \\sum_{i=1}^{n_f} \\sum_{j \\neq j^{\\prime}} x_{i j} x_{i j^{\\prime}} + \\lambda_e \\sum_{j=1}^{n_e} \\sum_{i \\neq i^{\\prime}} x_{i j} x_{i^{\\prime} j}\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk.tokenize import sent_tokenize\n",
    "# import nltk\n",
    "# nltk.download('punkt')\n",
    "\n",
    "def tokenize_japanese(text):\n",
    "    return [sent.replace('\\n', '') + '。' for sent in text.split('。')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "morphemes_en = sent_tokenize(original_text)\n",
    "morphemes_ja = tokenize_japanese(japanese_text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "def make_qubo_v1(sentences, lam_f=1.0, lam_e=1.0):\n",
    "    n_f, n_e = 0, 0\n",
    "\n",
    "    Q = defaultdict(lambda: 0)\n",
    "    for i in range(n_f):\n",
    "        for j in range(n_e):\n",
    "            k = i * n_e + j\n",
    "            Q[(k, k)] -= sentences[i][j]\n",
    "\n",
    "            for j_prime in range(j+1, n_e):\n",
    "                l = i * n_e + j_prime\n",
    "                Q[(l, k)] += lam_f\n",
    "\n",
    "            for i_prime in range(i+1, n_f):\n",
    "                l = i_prime * n_e + j\n",
    "                Q[(k, l)] += lam_e\n",
    "\n",
    "    return Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "import dimod\n",
    "\n",
    "\n",
    "qubo = make_qubo(sentences=[], lam_f=1.0, lam_e=1.0)\n",
    "bqm = dimod.BinaryQuadraticModel.from_qubo(qubo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sampler = dimod.SimulatedAnnealingSampler()\n",
    "results = sampler.sample(bqm, num_reads=10, num_sweeps=1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Moore 2002\n",
    "\n",
    "Reference: [Fast and Accurate Sentence Alignment of Bilingual Corpora](https://www.microsoft.com/en-us/research/wp-content/uploads/2002/10/sent-align2-amta-final.pdf)\n",
    "\n",
    "## IP formulation\n",
    "\n",
    "Next, consider the case where documents F and E are each divided into a series of the same number of sentences and a one-to-one mapping is required for the series of minutes.\n",
    "\n",
    "$$\n",
    "\\begin{array}{lll}\\text { maximize } & \\sum_{1 \\leq i \\leq j \\leq n_{f}} \\sum_{1 \\leq k \\leq l \\leq n_{e}} w_{i j k l} x_{i j k l} \\\\ \\text { subject to } & \\sum_{i \\leq p \\leq j 1 \\leq k \\leq l \\leq n_{e}} x_{i j k l}=1, & p=1, \\ldots, n_{f} \\\\ \\sum_{1 \\leq i \\leq j \\leq n_{f}} \\sum_{k \\leq q \\leq l} x_{i j k l}=1, & q=1, \\ldots, n_{e} \\\\ & x_{i j k l} \\in\\{0,1\\}, & 1 \\leq i \\leq j \\leq n_{f}, 1 \\leq k \\leq l \\leq n_{e}\\end{array}\n",
    "$$\n",
    "\n",
    "## QUBO formulation\n",
    "\n",
    "$$\n",
    "\\begin{array}{ll}\n",
    "\\text { minimize } H({\\bf x}) & = - \\sum_{i=1}^{n_{f}} \\sum_{j=1}^{n_{e}} s_{i j} x_{i j} \\\\ & + \\lambda_f \\sum_{i=1}^{n_f} \\sum_{j \\neq j^{\\prime}} x_{i j} x_{i j^{\\prime}} + \\lambda_e \\sum_{j=1}^{n_e} \\sum_{i \\neq i^{\\prime}} x_{i j} x_{i^{\\prime} j}\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_qubo_v2(sentences, lam_f=1.0, lam_e=1.0):\n",
    "    n_f, n_e = 0, 0\n",
    "\n",
    "    Q = defaultdict(lambda: 0)\n",
    "    for i in range(n_f):\n",
    "        for j in range(n_e):\n",
    "            k = i * n_e + j\n",
    "            Q[(k, k)] -= sentences[i][j]\n",
    "\n",
    "            for j_prime in range(j+1, n_e):\n",
    "                l = i * n_e + j_prime\n",
    "                Q[(l, k)] += lam_f\n",
    "\n",
    "            for i_prime in range(i+1, n_f):\n",
    "                l = i_prime * n_e + j\n",
    "                Q[(k, l)] += lam_e\n",
    "\n",
    "    return Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "qubo = make_qubo(sentences=[], lam_f=1.0, lam_e=1.0)\n",
    "bqm = dimod.BinaryQuadraticModel.from_qubo(qubo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sampler = dimod.SimulatedAnnealingSampler()\n",
    "results = sampler.sample(bqm, num_reads=10, num_sweeps=1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
